/*
 * int_map.c
 *
 *  Created on: 2012-8-29
 *      Author: lin
 */

#include "int_map.h"
#include "util/util_number.h"

#define Map int_map_t
#define Entry int_map_entry_t
#define INT_MAP_MAX_CAPACITY INT32_MAX

static inline void _add_entry(Entry** table, Entry* e, uint32_t idx) {
    e->next = table[idx];
    table[idx] = e;
}

Map* int_map_new0(uint32_t capacity, float factor) {
    assert(factor > 0 && factor <= 1);
    uint32_t pc = number_next_power(capacity, DEF_INT_MAP_CAPACITY,
            INT_MAP_MAX_CAPACITY);
    Entry ** table = zcalloc(sizeof(Entry*) * pc);
    Map* map = zcalloc(sizeof(Map));
    map->capacity = pc--;
    map->capacity_mask = pc;
    map->size = 0;
    map->table = table;
    map->factor = factor;
    map->thresold = (uint32_t)(map->capacity * factor);
    return map;
}
void int_map_clean(Map* imap) {
    uint32_t size = imap->size;
    uint32_t capacity = imap->capacity;
    Entry** table = imap->table;

    mixed_t_free_fn val_free_fn = imap->val_free_fn;

    for (uint32_t i = 0; i < capacity && size > 0; i++) {
        Entry *e, *nexte;
        e = table[i];
        while (e) {
            nexte = e->next;
            mixed_t_free(val_free_fn, e->val);
            zfree(e);
            e = nexte;
            --size;
        }
    }
    imap->size = 0;
}

void int_map_rehash(Map* imap, uint32_t newcapacity) {
    newcapacity = number_next_power(newcapacity, DEF_INT_MAP_CAPACITY,
            INT_MAP_MAX_CAPACITY);

    uint32_t capacity = imap->capacity;
    uint32_t size = imap->size;

    if (capacity == newcapacity || size == 0) {
        return;
    }
    Entry** table = imap->table;
    Entry** newtable = zcalloc(sizeof(Entry*) * newcapacity);
    uint32_t mask = newcapacity - 1;
    for (uint32_t i = 0; i < capacity && size > 0; i++) {
        Entry *e = table[i];
        Entry* next;
        while (e) {
            next = e->next;
            uint32_t idx = e->key & mask;
            _add_entry(newtable, e, idx);
            e = next;
            --size;
        }
    }
    zfree(imap->table);
    imap->table = newtable;
    imap->capacity = newcapacity;
    imap->capacity_mask = mask;
    imap->thresold = newcapacity * imap->factor;
}

static inline Entry* _map_add(Map* imap, uint32_t key, mixed_t val) {
    Entry** table = imap->table;
    uint32_t idx = key & imap->capacity_mask;
    Entry* e = _int_map_find_entry(idx, table, key, NULL);
    if (e) {
        return e;
    }

    e = zmalloc(sizeof(Entry));
    e->key = key;
    e->val = val;
    _add_entry(table, e, idx);
    if (++imap->size > imap->factor) {
        int_map_rehash(imap, imap->capacity >> 1);
    }
    return NULL;
}

int int_map_put_absent(Map* imap, uint32_t key, mixed_t val) {
    Entry* e = _map_add(imap, key, val);
    return e ? INT_MAP_EXIST : INT_MAP_ABSENT;
}

int int_map_put(Map* imap, uint32_t key, mixed_t val) {
    Entry* e = _map_add(imap, key, val);
    if (!e) {
        //not exist
        return INT_MAP_ABSENT;
    }
    Entry** table = imap->table;
    uint32_t idx = key & imap->capacity_mask;
    Entry* e = _int_map_find_entry(idx, table, key, NULL);
    mixed_t dupto = val;
    mixed_t_dup_fn dup_fn = imap->val_dup_fn;
    if (dup_fn && dup_fn(val, &dupto)) {
        return INT_MAP_ERR;
    }
    mixed_t_free(imap->val_free_fn, e->val);
    e->val = dupto;
    return INT_MAP_EXIST;
}

static int _map_remove(Map* imap, uint32_t key, int nofree) {
    Entry** table = imap->table;
    uint32_t idx = key & imap->capacity_mask;
    Entry** prev;
    Entry* e = _int_map_find_entry(idx, table, key, prev);
    if (!e) {
        return INT_MAP_ABSENT;
    }
    if (*prev != NULL) {
        **prev->next = e->next;
    } else {
        table[idx] = e->next;
    }

    if (!nofree) {
        mixed_t_free(imap->val_free_fn, e->val);
    }

    zfree(e);
    --imap->size;
    return INT_MAP_EXIST;

}
int int_map_remove(Map* imap, uint32_t key) {
    return _map_remove(imap, key, 0);
}
int int_map_remove_nofree(Map* imap, uint32_t key) {
    return _map_remove(imap, key, 1);
}

Entry* int_map_begin(Map *imap){
    uint32_t size = imap->size;
    if (size == 0) {
        return NULL;
    }
    uint32_t capacity = imap->capacity;
    Entry **table = imap->table;
    for (uint32_t i = 0; i < capacity; i++) {
        if (table[i]) {
            return table[i];
        }
    }
    return NULL;
}
Entry* int_map_next(Map *imap, Entry* cur){
    if (cur->next) {
          return cur->next;
      }
      uint32_t idx = cur->key & imap->capacity_mask;
      uint32_t capacity = imap->capacity;
      Entry **table = imap->table;
      for (uint32_t i = idx + 1; i < capacity; i++) {
          if (table[i]) {
              return table[i];
          }
      }
      return NULL;
}
